# -*- coding: utf-8 -*-


# 冒泡排序
def bubble_sort(array):
    n = len(array)
    k = n - 1
    for i in range(0, n):
        flag = 0
        pos = 0
        for j in range(0, k - i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                flag = 1
                pos = j
        if flag == 0:
            break
        k = pos


# 双向冒泡
def binary_bubble_sort(array):
    n = len(array)
    left = 0
    right = n - 1
    flag = 0
    while left < right:
        for i in range(left, right):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                flag = 1
        right -= 1
        if flag == 0:
            break
        for i in range(right, left, -1):
            if array[i] < array[i - 1]:
                array[i], array[i - 1] = array[i - 1], array[i]
                flag = 1
        left += 1
        if flag == 0:
            break


def partition(array, start, end):
    if start >= end:
        return
    mid = array[start]
    low = start
    high = end
    while low < high:
        while low < high and array[high] >= mid:
            high -= 1
        array[low] = array[high]
        while low < high and array[low] < mid:
            low += 1
        array[high] = array[low]
    array[low] = mid
    partition(array, start, low - 1)
    partition(array, low + 1, end)


def quick_sort(array):
    n = len(array)
    partition(array, 0, n - 1)


arr = [1, 2, 3, 5, 7, 4, 8, 9, 10]
quick_sort(arr)
print(arr)
